import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ClassName LC52
 * @Author ykx
 * @Date 2024/3/27 20:14
 * @Version 1.0
 */
public class LC52 {
    public static void main(String[] args) {
        LC52 lc52 = new LC52();
        System.out.println(lc52.totalNQueens(6));
    }

    public int totalNQueens(int n) {
        // 数组存储皇后位置(位于不同行)
        int[] queens = new int[n];
        List<int[]> result = new ArrayList<>();
        solve(n, 0, queens, result);
        for (int i = 0; i < result.size(); i++) {
            System.out.println(Arrays.toString(result.get(i)));
        }
        return result.size();
    }

    /**
     * 摆放皇后
     */
    public void solve(int n, int i, int[] queens, List<int[]> result) {
        if (n == i) {
            // 递归出口
            print(queens);
            result.add(queens);
        } else {
            for (int j = 0; j < queens.length; j++) {
                queens[i] = j;
                if (isValid(queens, i)) {
                    solve(n, i + 1, queens, result);
                }
            }
        }
    }

    /**
     * 判断当前已经摆放的i个皇后位置是否有效
     *
     * @param queens 皇后的存放位置
     * @return boolean
     */
    public boolean isValid(int[] queens, int i) {
        for (int k = 0; k <= i; k++) {
            for (int j = k + 1; j <= i; j++) {
                if (queens[k] == queens[j] || Math.abs(k - j) == Math.abs(queens[k] - queens[j])) {
                    // queens[k] == queens[j] 说明位于同一列
                    // Math.abs(k - j) == Math.abs(queens[k] - queens[j]) 说明俩皇后连线平行（重合）于对角线
                    return false;
                }
            }
        }
        return true;
    }

    public void print(int[] queens) {
        System.out.println(Arrays.toString(queens));
    }

}
